\section{Introduction}

Not all important information can be easily found, especially on a global scale when there is no one centralized database to fall back on.
The information which we consider in this paper is found in documents which lack the highly connected nature of hypertext, where pages routinely reference many other pages.
This problem is exacerbated when multiple writers and multiple readers all expect good consistency.
%and may prove especially difficult to keep track of.
%And then search gets even worse! %% C: What does this mean? Worse that what? Worse than not being found? "And then" implies after something else, after what?
Furthermore, in many situations information is not repeated across multiple documents: data only exists in one particular document, and this one document may be constantly edited.
Our challenge is thus naming one correct document in a sea of false leads in a distributed manor, and then allowing for the controlled editing of this information.

% without an easy way of indexing all of the available information,

As a motivating example, consider the United Nations. 
The UN has offices all over the world, each of which is dedicated to producing information.
The documents which each office produces frequently may not reference other documents. 
Documents have to be available on demand to anyone who asks. However, a hot-cold distribution of interest is expected, where most documents are seldom read and some few are frequently accessed.
Furthermore, while documents should be stored redundantly, they are not immutable; writes as well as reads must be expected.
And of course, all this has to be done on a budget.
This financial constraint combined with the large volume of documents make storing all information centrally (with  local cached copies for fast access) untenable.

%$\Box$ Scott, ideas for a citation here?

The problem we present above is twofold: first finding information and then retrieving that information. 
There are several further challenges in the second part.
First, concurrency must be upheld while supporting writes as well as reads.
Also, security, privacy and user privilege systems are expected, along with reasonable performance.

% Furthermore, all of this needs to be able to be developed and deployed on a budget.

Thus, any complete solution has three features as goals:

\begin{enumerate}

\item  {\bf Filesystem Semantics}: Concurrency control and close-to-open consistency are essential to keep things manageable in a distributed system with many readers and writers.

\item
 {\bf Database-Style Indexing}: We need the ability to search on arbitrary file attributes and get good results quickly. 
 Additionally, Ringer's approach should work well even when information is found in only a few sources.
 %Ringer need to supports different ways of sorting content. 

\item
  {\bf Internet-Style Connectivity}: Files need to be available on demand, but only downloaded (a slow operation on a low bandwidth network) as needed. 
  Most files are expected to be accessed rarely.  

\end{enumerate}

A naive approach to this problem might be to simply rely on email to spread documents. 
This has the benefit of being easy to deploy, low cost and a process which (most) everyone understands. 
However, using this approach one has no idea what documents are out there -- one only knows what documents one has. 
As the number of files scales, this approach falls apart.

Another possible solution is to give each office a web-server and access to a VPN, and throw a search appliance on the resulting network.
However, because of the many formats which documents can take, the expected lack of references and the lack of redundancy, this approach does not work well \cite{Hawking:2004p3232}.

A third solution might be a decentralized peer to peer file-sharing network, in the manor of Frangipani\cite{Thekkath:1997p2547}.
This fails because of the search requirement: It is not enough to be able to read a document.
Users have to be able to find the document first.

%Another idea is for a centralized document repository to be created. However, at a global scale, not all users will have fast access, unless caching is used. %Caching makes it difficult to support filesystem semantics when users are actively reading and writing documents. Conversely, documents could be posted online, and then indexed using a PageRank-like algorithm. 
%We previously discussed the shortcomings of this approach.

The common thread here is that search is hard, especially when combined with concurrency and stability.

Our proposed solution, the Ringer system, works by adding a metadata superstructure onto a decentralized P2P network, in the process separating out the handling of data and metadata.
Clients transfer data directly between each other in a traditional P2P manner. 
Clients find each other via a graph of metadata servers (MDS) organized in parent/child relationships. 
The MDS graph can be arbitrarily organized. 
In general, parents know what files their kids have, but not more than that.
To facilitate search, we have explored topologies where MDSs are grouped into sparsely connected clusters or rings (hence the name Ringer for our project) connected by a few or even one top level MDS.
Ringer differs from other P2P systems such as Ivy\cite{Muthitacharoen:2002p1739} since while there is no single MDS, there is also not a complete lack of centrality. 
Our hybrid approach simplifies implementation and search while avoiding the bottlenecks caused by a single central MDS.

%  The goal of our architecture is to 
% Instead, we are investigating a third approach: 





